import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * @ClassName Offer_30
 * @Description 包含min函数的栈
 * @Author clockTown
 * @Date 2021/8/12 20:12
 * @Version 1.0
 */
class Offer30 {
}

/**
 * v0 使用优先队列维护最小值，未 AC
 */
class MinStackV0 {

    private PriorityQueue<Integer> priorityQueue;
    private Deque<Integer> stack;

    /**
     * initialize your data structure here.
     */
    public MinStackV0() {
        this.priorityQueue = new PriorityQueue<>((o1, o2) -> (o1 - o2));
        this.stack = new LinkedList<>();
    }

    public void push(int x) {
        priorityQueue.add(x);
        stack.push(x);
    }

    public void pop() {
        if (!stack.isEmpty()) {
            int peek = stack.pop();
            priorityQueue.remove(peek);
        }
    }

    public int top() {
        return stack.isEmpty() ? -1 : stack.peek();
    }

    public int min() {
        return priorityQueue.isEmpty() ? -1 : priorityQueue.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

/**
 * v1 双栈
 */
class MinStackV1 {

    private Deque<Integer> stack;
    private Deque<Integer> minValue;

    /**
     * initialize your data structure here.
     */
    public MinStackV1() {
        this.stack = new LinkedList<>();
        this.minValue = new LinkedList<>();
    }

    public void push(int x) {
        stack.push(x);
        if (minValue.isEmpty() || minValue.peek() >= x){
            minValue.push(x);
        }
    }

    public void pop() {
        if (!stack.isEmpty()) {
            if (!minValue.isEmpty() && minValue.peek().equals(stack.pop())){
                minValue.pop();
            }
        }
    }

    public int top() {
        return stack.isEmpty() ? -1 : stack.peek();
    }

    public int min() {
        if (minValue.isEmpty()){
            if (stack.isEmpty()){
                return -1;
            }else {
                return stack.peek();
            }
        }
        return minValue.peek();
    }
}